/*
https://leetcode.cn/problems/magnetic-force-between-two-balls/submissions/567681112/
*/
class Solution {
public:
    int maxDistance(vector<int>& position, int m) {
        sort(position.begin(),position.end());
        int len=position.size()-1;
        int diff=position[len]-position[0];//最大
        int min=1000000000;
        for(int i=0;i<len;++i){
            if(min>position[i+1]-position[i])
            min=position[i+1]-position[i];
        }
        int l=min,r=diff/(m-1);
        while(l<=r){
            long long mid=(l+r)/2;
            int count=0;
            int target=position[0]+mid;
            for(int i=0;i<len;++i){
                if(position[i]<target&&position[i+1]>=target) {
                    ++count;
                    target=position[i+1]+mid;
                }
            }
            if(count>=m-1){
                l=mid+1;
            }
            else {
                r=mid-1;
            }
        }
        return l-1;
    }
};